package NodeList;

class MyLinkedList {
    int size;
    ListNode head, tail;


    public MyLinkedList(){
        this.size = 0;
        this.head = new ListNode();
        this.tail = new ListNode();
        head.next = tail;
        tail.prev = head;

    }
    public int get(int index) {
        int count = 0;
        if (index < 0 || index >= this.size){
            return -1;
        }
        ListNode node = this.head.next;
        while (node != tail ){
            if (count == index){
                break;
            }
            count++;
            node = node.next;
        }
        return node.val;
    }
    
    public void addAtHead(int val) {
        ListNode newNode = new ListNode();
        newNode.val = val;
        if (head.next == tail){
            newNode.prev = head;
            newNode.next = tail;
            head.next = newNode;
            tail.prev = newNode;
        } else {
            newNode.prev = head;
            newNode.next = head.next;
            head.next.prev = newNode;
            head.next = newNode;
        }
        size++;
    }
    
    public void addAtTail(int val) {
        ListNode newNode = new ListNode();
        newNode.val = val;
        if (tail.prev == head){
            newNode.prev = head;
            newNode.next = tail;
            head.next = newNode;
            tail.prev = newNode;
        } else {
            newNode.prev = tail.prev;
            newNode.next = tail;
            tail.prev.next = newNode;
            tail.prev = newNode;
        }
        size++;
    }
    
    public void addAtIndex(int index, int val) {
        ListNode searchNode = new ListNode();
        if (index > size){
            return;
        } else if (index == 0){
            addAtHead(val);
        } else if (index == size){
            addAtTail(val);
        } else if (index >= size/2){
            searchNode = tail.prev;
            int c = 0;
            while (searchNode != head){
                c++;
                if (c == size-index){
                    ListNode node = new ListNode();
                    node.val = val;
                    node.prev = searchNode.prev;
                    node.next = searchNode;
                    searchNode.prev.next = node;
                    searchNode.prev = node;
                    break;
                }
                searchNode = searchNode.prev;
            }
            size++;
        } else if (index < size/2){
            searchNode = head.next;
            int c = 0;
            while (searchNode != tail){
                if (c == index){
                    ListNode node = new ListNode();
                    node.val = val;
                    node.prev = searchNode.prev;
                    node.next = searchNode;
                    searchNode.prev.next = node;
                    searchNode.prev = node;
                    break;
                }
                c++;
                searchNode = searchNode.next;
            }
            size++;
        }
    }
    
    public void deleteAtIndex(int index) {
        ListNode searchNode = new ListNode();
        if (index >= 0 && index < size){
            if (index >= size/2){
                searchNode = tail.prev;
                int c = 0;
                while (searchNode != head){
                    c++;
                    if (c == size-index){
                        searchNode.prev.next = searchNode.next;
                        searchNode.next.prev = searchNode.prev;
                        break;
                    }
                    searchNode = searchNode.prev;
                }
                size--;
            } else if (index < size/2){
                searchNode = head.next;
                int c = 0;
                while (searchNode != tail){
                    if (c == index){
                        searchNode.prev.next = searchNode.next;
                        searchNode.next.prev = searchNode.prev;
                        break;
                    }
                    c++;
                    searchNode = searchNode.next;
                }
                size--;
            }
        }
    }
}